In processing a document image a common requirement is to isolate text objects and then cluster them into blocks of text (e.g. paragraphs, addresses, form fields etc). The first step is to extract the text objects resulting in a binary image. Clustering the binary text objects together then produces text blocks. A simple clustering technique would be to merge any neighbouring binary objects where the gap between the objects is less than a given limit. In documents where the blocks of text of interest are well separated from other text blocks, this technique is usually successfully. For example, for a simple white envelope with an address and a single stamp or indicia, the distance between letters in the address is usually significantly less than the distance between the address and the other objects on the envelope. Thus it is easy to set a distance limit in the merging that will cluster together the text objects of the address but not connect the address to the stamp or indicia which is significantly further away. However, on more complex document images, text block identification is not so simple. For example, many mail items have additional text and designs printed on them. Also, some mail items come in transparent packaging which allows the content to be seen from the outside. It is a more difficult task to identify likely candidates for an address from images of these types of documents.
Complex document images often require different processing to the more simple images to identify and read, e.g. address information. Accordingly in the case of processing mail we have proposed in our British Patent Application No. [------] filed on the same day as the current application, a method and apparatus for identifying the degree of complexity in an image of a mail item, so that subsequent processing is appropriate to the image.
The merging of binary text objects from a document image connects together text objects that have a gap between them that is less than a distance limit. The merging distance limit needs to be appropriate to the text. If the distance limit is too small then some text within a block remains un-merged and isolated. If the distance limit is too large then over-merging occurs where distinct text blocks are incorrectly linked. The appropriate merging distance limit is usually proportional to the font size of the text in the document being processed. In simple documents where the text block of interest is well separated from other objects in the image the setting of the merging distance limit is easy. However, in complex image documents there may be text objects of a variety of fonts, sizes and orientations. With such images the clustering of text objects may not be possible with a single merging distance limit, since a limit which is too small for some text objects in the document may be too large for text in another part of the image. In such situations the clustering of text objects into text blocks usually becomes more complex as techniques should connect together only text of the same font, orientation, etc.
We have appreciated that the process of clustering related text objects can be made more computationally efficient and successful by approaching it as a segmentation problem followed by a simple merging routine, rather than investing in a complicated or computationally expensive clustering technique. Accordingly, a preferred embodiment of the present invention first segments the binary image of the text objects in such a way as to separate text objects that are close but unrelated. This effectively separates the complex image into separate simple images where a coarse computationally light merge can be applied to successfully cluster the text objects into relevant text blocks. In a preferred embodiment of the invention, the information used to segment the binary text objects is taken from the original greyscale or colour document image. Items of different greyscale or colour value are assumed to be unrelated. Items on different greyscale or colour value are assumed to be unrelated.
There are a number of local text attributes that generally remain constant for a text block in a document image. The useful measures that could be extracted from the binary text objects such as font, orientation and alignment are usually computationally demanding to calculate. The local text attribute used in this preferred embodiment is a local measure of the text's original colour or greyscale value. This is computationally easy to measure but requires the interrogation of the original image. This is different to most document image processing techniques, which discard the original image information once the binary text objects have been extracted. In addition this invention also uses a global document image attribute to separate unrelated text blocks. This is the background colour in the document, which again in standard techniques would have been lost in discarding the original image. These measures are useful as long as the assumptions that text blocks are printed in a consistent colour and on a consistent background hold for the document image being processed.
The invention is defined with more precision in the appended claims to which reference should now be made.